package com.study.algorithm.ordinaryArray;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0){
            return new int[0][2];
        }
        //按照区间的起始位置排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int []> merged  = new ArrayList<>(); //创建一个集合，存储合并后的区间
        merged.add(intervals[0]);
        for(int i=1; i<intervals.length; i++){
            int [] current= intervals[i];
            int [] last = merged.get(merged.size()-1);
            //判断当前区间的起始位置是否小于等于前一个区间的结束位置
            if(current[0] <= last[1]){
                //合并区间，右端点取最大值
                last[1] = Math.max(last[1], current[1]);
            }
            else {
                //没有重叠，添加到集合中
                merged.add(current);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }


    public static void main(String[] args) {
        int[][] intervals = {{4,3},{2,6},{8,10},{15,18}};
        MergeIntervals mergeIntervals = new MergeIntervals();
        int[][] result = mergeIntervals.merge(intervals);
        System.out.println(Arrays.deepToString(result));
    }
}
